'''
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

 

示例 1:

输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
示例 2:

输入: n = 1, k = 1
输出: [[1]]
 

提示:

1 <= n <= 20
1 <= k <= n

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/uUsW3B
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
'''
class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        res = []

        def func(l):
            hx_list = list(range(l[-1] + 1, n + 1))
            if len(l) < k:
                for hx_num in hx_list:
                    tmp = []
                    tmp = tmp + l + [hx_num]
                    res.append(tmp)
                    func(tmp)
            elif len(hx_list) == 0:
                return
            else:
                return hx_list

        for i in range(1, n - k + 2):
            if k==1:
                res.append([i])
            else:
                func([i])
        return [r for r in res if len(r)==k]

n = 3
k = 3
Solution().combine(n,k)